//Sat 19 Dec 2009 11:32:42 PM CST 
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class SortingGame
{
public:
	int fewestMoves(vector <int> board, int k)
	{
		map<vector<int>, int> mp;
		mp[board] = 0;
		
		queue<vector<int> > q;
		q.push(board);
		
		while(!q.empty())
		{
			vector<int> temp = q.front();
			q.pop();
			
			bool flag = true;
			for(int i=0; i+1<temp.size(); i++)
			{
				if(temp[i] > temp[i+1])
				{
					flag = false;
					break;
				}
			}
			if(flag) return mp[temp];
			
			for(int i=0; i+k<=temp.size(); i++)
			{
				vector<int>::iterator it;
				vector<int> tmp = temp;
				it = tmp.begin();
				cout << *(it+i) << ", " << *(it+i+k-1) << endl;
				reverse(tmp.begin()+i, tmp.begin()+i+k);
				//The range used is [first,last);
				if(mp[tmp] == 0)
				{
					q.push(tmp);
					mp[tmp] = mp[temp] + 1;
				}
			}
		}
		return -1;
	}
};
